package ArrayList;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Classname JZ40最小的k个数
 * @Description TODO
 * @Date 2022/12/7 10:18
 * @Created by xjl
 */
public class JZ40最小的k个数 {

    /**
     * @description 使用的数组的排序的思路  时间：O(nLog（n）) 空间：O(k)
      * @param: arr
     * @param: k
     * @date: 2022/12/7 10:50
     * @return: int[]
     * @author: xjl
    */
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] result=new int[k];
        int index=0;
        while (index<k){
            result[index]=arr[index];
            index++;
        }
        return result;
    }

    public int[] getLeastNumbers3(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOf(arr,k);
    }

    /**
     * @description 利用小顶堆的数据结构来实现数据找到最小的那几个数据
      * @param: arr
     * @param: k
     * @date: 2022/12/7 11:06
     * @return: int[]
     * @author: xjl
    */
    public int[] getLeastNumbers2(int[] arr, int k) {
        int[] vec=new int[k];
        if (k==0){
            return vec;
        }
        // 构建的是一个的优先队列  小根堆数据结构
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        // 添加k个值到小根堆中
        for (int i=0;i<k;i++){
            queue.offer(arr[i]);
        }
        for (int i=k;i<arr.length;i++){
            if (queue.peek()>arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i=0;i<k;i++){
            vec[i]=queue.poll();
        }
        return vec;
    }

    /**
     * @description 手动实现快排的思想来完成
      * @param: arr
     * @param: k
     * @date: 2022/12/7 11:30
     * @return: int[]
     * @author: xjl
    */
    public int[] getLeastNumbers4(int[] arr, int k) {
        if (k >= arr.length) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            // j 向左边里面走
            while (i < j && arr[j] >= arr[l]) {
                j--;
            }
            // i向右边走
            while (i < j && arr[i] <= arr[l]) {
                i++;
            }
            swap(arr, i, j);
        }
        // 交换的是的i 和左边选定的基准值
        swap(arr, i, l);
        if (i > k) {
            return quickSort(arr, k, l, i - 1);
        }
        if (i < k) {
            return quickSort(arr, k, i + 1, r);
        }
        // 如果是的i=k  那就表前k个数据是有序的。
        return Arrays.copyOf(arr, k);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    @Test
    public void test(){
        int[] leastNumbers4 = getLeastNumbers4(new int[]{2, 4, 1, 0, 3, 5}, 2);

    }
}
